package DayThree;

import java.util.*;
/*给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
        例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此
        输出2。*/

public class TestTwo {


    public static int[] guiBing(int[] arr,int left,int right){
        if(left==right){
            return new int[]{arr[left]};
        }
        int mid = left+(right-left)/2;
        int[] leftArr = guiBing(arr,left,mid);
        int[] rightArr = guiBing(arr,mid+1,right);
        arr = heBing(leftArr,rightArr);
        return arr;
    }

    private static int[] heBing(int[] leftArr, int[] rightArr) {
        int n = 0;
        int m = 0;
        int k = 0;
        int[] tmp = new int[leftArr.length+ rightArr.length];
        while(n<leftArr.length&&m<rightArr.length){
            if(leftArr[n]<rightArr[m]){
                tmp[k] = leftArr[n];
                k++;
                n++;
            }else{
                tmp[k] = rightArr[m];
                k++;
                m++;
            }
        }
        if(n< leftArr.length) {
            while (n < leftArr.length) {
                tmp[k] = leftArr[n];
                k++;
                n++;
            }
        }else{
            while(m<rightArr.length){
                tmp[k] = rightArr[m];
                m++;
                k++;
            }
        }
        return tmp;
    }

    public static int[] InitArr(int[] arr){
        Scanner sc = new Scanner(System.in);
        for(int i =0;i<arr.length;i++){
            arr[i] = sc.nextInt();
            sc.nextLine();
        }
        return arr;
    }

    public static void main6(String[] args) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(1,3);
        map.put(2,1);
        map.put(8,7);
        map.put(5,6);
        Set<Integer> set=map.keySet();
        map.entrySet();
        List<Map.Entry<Integer,Integer>> list = new ArrayList(map.entrySet());
        Collections.sort(list, (o1, o2) -> (o2.getValue() - o1.getValue()));//升序
        System.out.println(list.get(0).getKey());
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            HashMap<Integer,Integer> map = new HashMap<>();
           int count = 1;
           int n = sc.nextInt();
           int[] arr = new int[n];
           arr = InitArr(arr);
           arr = guiBing(arr,0,arr.length-1);
           for(int i = 0;i<arr.length;i++){
               if(map.containsKey(arr[i])){
                   count++;
                   map.put(arr[i],count);
               }else{
                   count = 1;
                   map.put(arr[i],count);
               }
           }
            Set<Integer> set=map.keySet();
            map.entrySet();
            List<Map.Entry<Integer,Integer>> list = new ArrayList(map.entrySet());
            Collections.sort(list, (o1, o2) -> (o2.getValue() - o1.getValue()));//升序
            System.out.println(list.get(0).getKey());
        }
    }
}
